Lemme d'Euclide

Lemme d'Euclide

Soit \(a\) et \(b\) deux entiers naturels non nuls. Soit \(r\) le reste dans la division euclidienne de \(a\) par \(b\) .
On a \(\mathscr{D}(a;b)=\mathscr{D}(b;r)\) , et par conséquent, \(\mathrm{PGCD}(a;b)=\mathrm{PGCD}(b;r)\) .

Démonstration

On procède par double inclusion.

• \([\subset]\)  Montrons que \(\mathscr{D}(a;b) \subset \mathscr{D}(b;r)\) .
  Soit \(d \in \mathscr{D}(a;b)\) . Alors \(d\) divise \(a\) et \(b\) , donc il existe des entiers \(a'\) et \(b'\) tels que \(a=a'd\) et \(b=b'd\) .
  En notant \(q\) le quotient dans la division euclidienne de \(a\) par \(b\) , on a alors : \(\begin{align*} a=bq+r & \ \ \Longleftrightarrow \ \ a'd=b'dq+r \ \ \Longleftrightarrow \ \ d(a'-b'q)=r \end{align*}\)  
  donc \(d\) divise \(r\) , donc \(d \in \mathscr{D}(b;r)\) .
  Ceci étant valable pour tout \(d \in \mathscr{D}(a;b)\) , on en déduit que \(\mathscr{D}(a;b) \subset \mathscr{D}(b;r)\) .
  
• \([\supset]\) Montrons que \(\mathscr{D}(b;r) \subset \mathscr{D}(a;b)\) .
  Soit \(d \in \mathscr{D}(b;r)\) . Alors \(d\) divise \(b\) et \(r\) , donc il existe des entiers \(b'\) et \(r'\) tels que \(b=b'd\) et \(r=r'd\) .
  En notant \(q\) le quotient dans la division euclidienne de \(a\) par \(b\) , on a alors : 
  \(\begin{align*} a=bq+r & \ \ \Longleftrightarrow \ \ a=b'dq+r'd \ \ \Longleftrightarrow \ \ d(b'q+r')=a \end{align*}\)  
  donc \(d\) divise \(a\) , donc \(d \in \mathscr{D}(a;b)\) .
  Ceci étant valable pour tout \(d \in \mathscr{D}(b;r)\) , on en déduit que \(\mathscr{D}(b;r) \subset \mathscr{D}(a;b)\) .

On en déduit que \(\mathscr{D}(a;b)=\mathscr{D}(b;r)\) .

Comme \(a\) et \(b\) sont non nuls, les ensembles \(\mathscr{D}(a;b)\) et \(\mathscr{D}(b;r)\) admettent un plus grand élément (qui est le même puisque ces ensembles sont égaux), c'est-à-dire que l'on a \(\mathrm{PGCD}(a;b)=\mathrm{PGCD}(b;r)\) .